package com.itheima.datastructure.linkedlist;

/**
 * 合并两个有序链表 p1:[1,1,4,8,9,10,10] p2:[2,4,4]  合并后：[1,1,2,4,4,4,8,9,10,10]
 */
public class E06Leetcode21 {

    //创建新的节点【不推荐】
    public ListNode mergeTwoLists0(ListNode p1, ListNode p2) {

        // 创建一个新链表
        ListNode sn = new ListNode(-1, null);
        ListNode pre = sn;

        //当两个都不为null时，比较两个节点的值，将较小的节点添加到新链表，并移动到下一个节点
        ListNode curP1 = p1;
        ListNode curP2 = p2;
        while (curP1 != null && curP2 != null) {
            int val1 = curP1.val;
            int val2 = curP2.val;
            if (val1 < val2) {
                //构建一个新节点
                ListNode listNode = new ListNode(val1, null);
                //新节点添加到新链表
                pre.next = listNode;
                //pre移动
                pre = pre.next;
                //p1移动
                curP1 = curP1.next;
            } else if (val1 > val2) {
                // 构建一个新节点
                ListNode listNode = new ListNode(val2, null);
                //新节点添加到新链表
                pre.next = listNode;
                //pre移动
                pre = pre.next;
                //p2移动
                curP2 = curP2.next;
            } else {
                // 构建一个新节点，该节点的next指向新链表的头节点，pre移动
                ListNode n1 = new ListNode(val1, null);
                pre.next = n1;
                pre = pre.next;
                curP1 = curP1.next;

                // 构建一个新节点
                ListNode n2 = new ListNode(val1, null);
                pre.next = n2;
                pre = pre.next;
                curP2 = curP2.next;
            }
        }
        if (curP1 == null) {
            pre.next = curP2;
        }
        if (curP2 == null) {
            pre.next = curP1;
        }


        return sn.next;
    }

    /**
     * 创建一个新的链表，将两个链表合并
     *
     * @param p1
     * @param p2
     * @return
     */
    public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        ListNode s = new ListNode(-1, null);
        ListNode pre = s;

        //当两个都不为null时，比较两个节点的值，将较小的节点添加到新链表，并移动到下一个节点
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                //p1小，则将p1添加到新链表
                pre.next = p1;
                //移动p1
                p1 = p1.next;
            } else {
                //p2小，则将p2添加到新链表
                pre.next = p2;
                //移动p2
                p2 = p2.next;
            }
            //移动pre
            pre = pre.next;
        }
        //剩余的节点p1,直接添加到新链表
        if (p1 != null) {
            pre.next = p1;
        }
        //剩余的节点p2,直接添加到新链表
        if (p2 != null) {
            pre.next = p2;
        }
        return s.next;
    }


    /**
     * 递归函数应该返回：
     * - 更小的那个链表节点，并把它剩余节点与另一个链表再次递归
     * - 返回之前，更新此节点的next
     *
     * @param p1
     * @param p2
     * @return
     */
    public ListNode mergeTwoLists2(ListNode p1, ListNode p2) {
        if (p2 == null) {
            return p1;
        }
        if (p1 == null) {
            return p2;
        }
        if (p1.val < p2.val) {
            //p1的值小，p1作为头结点
            //更新p1的next
            p1.next = mergeTwoLists(p1.next, p2);
            //返回p1
            return p1;
        } else {
            //p2的值小，p2作为头结点
            //更新p2的next
            p2.next = mergeTwoLists(p1, p2.next);
            //返回p2
            return p2;
        }
    }

    public static void main(String[] args) {
        ListNode p1 = ListNode.of(1, 1, 4, 8, 9, 10, 10);
        ListNode p2 = ListNode.of(2, 4, 4);

//        ListNode p1 = new ListNode(1,
//                new ListNode(3,
//                        new ListNode(8,
//                                new ListNode(9,
//                                        new ListNode(10, null)
//                                )
//                        )
//                )
//        );
//        ListNode p2 = new ListNode(2, new ListNode(4, null));
        System.out.println(p1);
        System.out.println(p2);
        System.out.println(new E06Leetcode21()
                .mergeTwoLists0(p1, p2));
    }
}
